package com.Q02;

import com.common.ListNode;

/**
 * @version v1.0.0
 * 创建时间：2022/6/24 10:41
 */
public class Q02_06 {
    public boolean isPalindrome(ListNode head) {
        // 找到链表中点，然后将后半反转再和前半段依次判断
        if(head==null||head.next==null) return true;
        ListNode pre= new ListNode(-1);
        pre.next = head;
        ListNode p1=pre,p2=pre;
        while(p2.next!=null&&p2.next.next!=null){
            p1 = p1.next;
            p2 = p2.next.next;
        }
        p2 = p1.next;
        p1.next = null;
        p1 = pre.next;
        p2 = reverse(p2);

        while(p1!=null&& p2!=null){
            if(p1.val!=p2.val) return false;
            p1 = p1.next;
            p2 = p2.next;
        }
        return true;
    }

    public ListNode reverse(ListNode head){
        if(head.next==null){
            return head;
        }
        ListNode p = reverse(head.next);
        head.next.next = head;
        head.next = null;
        return p;
    }

    public static void main(String[] args) {
        new Q02_06().isPalindrome(new ListNode(0,new ListNode(0)));
    }
}
